#include <algorithm>
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:

    bool ans=true;
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return ans;
    }
    
    int dfs(TreeNode* u)
    {
        if(u==NULL) return 0;
        int lh=0, rh=0;
        if(u->left) lh=dfs(u->left);
        if(u->right) rh=dfs(u->right);
        if(abs(lh-rh)>1) ans=false;
        return max(lh, rh)+1;
    }
};